package com.itheima.algorithm.recursion_multi;

import java.util.Arrays;

/**
 * @author tantao
 * @version 1.0
 * @description: 杨辉三角
 * @date 2025/8/21 14:59
 */
public class E03PascalTriangle01 {

    public static void main(String[] args) {
        //自己写的
//        printTriangle(new int[]{1}, 10);


        //递归
//        print(10);

        //递归+二维数组缓存
//        printWithCache(10);

        //一行缓存(动态规划)
        printWithRow(10);
    }

    static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 2;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    static void print(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element(i, j));
            }
            System.out.println();
        }
    }


    private static int element(int i, int j) {
        if (j == 0 || i == j) {
            return 1;
        }
        return element(i - 1, j - 1) + element(i - 1, j);
    }


    static void printWithCache(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", elementWithCache(i, j, triangle));
            }
            System.out.println();
        }
    }


    private static int elementWithCache(int i, int j, int[][] triangle) {
        //使用缓存
        if (triangle[i][j] > 0) {
            return triangle[i][j];
        }

        if (j == 0 || i == j) {
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] = elementWithCache(i - 1, j - 1, triangle) + elementWithCache(i - 1, j, triangle);
        return triangle[i][j];
    }


    // 打印杨辉三角
    static void printTriangle(int[] preLine, int n) {
        if (preLine.length == 1) {
            System.out.println(Arrays.toString(preLine));
        }
        if (preLine.length == n) {
            return;
        }
        int[] current = new int[preLine.length + 1];
        for (int i = 0; i < current.length; i++) {
            if (i == 0 || i == current.length - 1) {
                current[i] = 1;
            } else {
                current[i] = preLine[i - 1] + preLine[i];
            }
        }
        System.out.println(Arrays.toString(current));
        printTriangle(current, n);


    }

    static void printWithRow(int n) {
        int[]row = new int[n];
        for (int i = 0; i < n; i++) {
            creatRow(row, i);
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", row[j]);
            }
            System.out.println();
        }
    }

    /**
     * 生成每一行的数据，并且将数据存储在数组中
     *
     * @param row
     * @param i
     */
    static void creatRow(int[] row, int i) {
        if (i == 0) {
            row[0] = 1;
            return;
        }
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }


}
